package bin_tree.leetcode;

/**
 * @author shkstart
 * 根据前序和中序的遍历结果还原二叉树
 * @create 2022-10-24-17:48
 */
public class Num105 {

    //    当前处理到前序遍历的哪个位置
    int index = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeInternal(preorder, inorder, 0, inorder.length);
    }
    /*
    根据传入的前序遍历和中序遍历的部分区间
    左区间连接到根节点的左侧
    右区间连接到根节点的右侧
    preOrder 前序遍历结果
    inOrder  中序遍历结果
    */

    public TreeNode buildTreeInternal(int[] preOrder, int[] inOrder, int left, int right) {
//        边界
        if (left >= right) {
//            空区间，说明中序结果为空，空树
            return null;
        }
        if (index >= preOrder.length) {
//            所有节点已经处理完毕
            return null;
        }
//        此时前序结果还有没处理的元素，从index位置获取一个元素构建根节点
        TreeNode root = new TreeNode(preOrder[index]);
//        继续处理下一个节点
        index++;
//        处理左树
//        拿着根节点root.val去从中序遍历中找到该值对应的索引pos
        int pos = find(inOrder,left,right,root.val);
//        左树
        root.left = buildTreeInternal(preOrder,inOrder,left,pos);
        root.right = buildTreeInternal(preOrder,inOrder,pos+1,right);
        return root;
    }

    /*从当前中序遍历中寻找root.val对应的索引值
    inOrder,
     left
      right
      val

     */
    private int find(int[] inOrder, int left, int right, int val) {
        for (int i = left; i < right; i++) {
            if (inOrder[i] == val) {
                return i;
            }
        }
        return -1;
    }


}
